3.1 栈

栈是一种线性数据结构，本节我们将针对栈的基础概念、实现原理以及Go语言的栈实现进行讲解。

本节代码存放目录为 lesson4

概念及原理

栈是一种线性数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。

也就是说，最后进入栈的数据最先被弹出。栈的基本操作包括：

• 压栈（Push）：将元素放入栈的顶部。

• 出栈（Pop）：从栈的顶部移除元素。

• 查看栈顶元素（Peek）：获取栈顶元素但不移除它。

简单来说，栈就像是口红一样的，最外面的被最先使用掉；或者说就像是叠书一样，最先放的书压在了最下面。

基于栈的结构设计，栈的操作只能在栈顶进行。也就是说当我们需要添加、删除元素时，那只能在栈顶操作，不能在栈中间或者底部进行操作。

栈的简单结构示意图如下所示：

栈顶
+-------+
|   4   | <- 出栈
+-------+
|   3   |
+-------+
|   2   |
+-------+
|   1   |
+-------+
栈底

• 压栈：将元素 4 压入栈顶。

• 出栈：弹出栈顶元素 4。

• 查看栈顶元素：可以查看 4，但不移除它。

栈在很多算法和场景中都有广泛的应用，主要用于需要回溯、递归或顺序反转的场景：

• 递归调用：编译器会使用栈来存储函数的调用信息，函数的递归调用依赖栈的后进先出特性。

• 表达式求值：如四则运算的求值或逆波兰表达式的计算。

• 括号匹配：用于验证表达式中括号是否匹配（如编译器中）。

• 浏览器的回退功能：浏览器记录历史页面时使用栈来管理用户的页面回退。

Go语言的实现

Go语言中我们可以通过切片来实现类似于栈的结构，代码如下所示：

type Stack struct {
    elements []int
}

func (s *Stack) Push(ele int) {
    s.elements = append(s.elements, ele)
}

func (s *Stack) Pop() int {
    if len(s.elements) == 0 {
        fmt.Println("栈为空")
        return -1
    }
    top := s.elements[len(s.elements)-1]

    // 移除栈顶元素
    s.elements = s.elements[:len(s.elements)-1]
    return top
}

func (s *Stack) Peek() int {
    if len(s.elements) == 0 {
        fmt.Println("栈为空")
        return -1
    }
    return s.elements[len(s.elements)-1]
}

func main() {
    stack := Stack{}
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)

    fmt.Printf("pop-> %d\n", stack.Pop())
    fmt.Printf("peek-> %d\n", stack.Peek())
}

执行输出如下所示：

pop-> 3
peek-> 2

在上面的代码中，其实我们就是通过一个切片来实现了栈，每次操作的都是切片的最后一个元素，也就相当于是栈的栈顶。

小结

栈是最基本的线性数据结构之一，在许多算法和编程场景中有着广泛的应用。

关于本节总结如下：

• 栈是一种LIFO结构，最后入栈的元素最先出栈。

• 所有的插入和删除操作都只能在栈顶进行，无法访问栈底元素。

• 栈在需要回溯、递归或逆序操作的场景中表现良好。